home *** CD-ROM | disk | FTP | other *** search
/ Mac Mania 5 / MacMania 5.toast / / Tools&Utilities / Plotfoil 3.2 / spline.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-19  |  4.5 KB  |  126 lines  |  [TEXT/MMCC]
  1. /*
  2.  * Code to generate bezier control points to interpolate between points.
  3.  * Copyright Shamim Mohamed 1991
  4.  *
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2 of the License, or
  8.  * (at your option) any later version.
  9.  *
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  *
  19.  * shamim@cs.arizona.edu
  20.  * Shamim Mohamed
  21.  * Dept of Computer Science
  22.  * University of Arizona
  23.  * Tucson, AZ 85721
  24.  *
  25.  * --------------------------------------------------------------------------
  26.  *
  27.  * Inputs: an array of points, the number of points, two fudge-factors,
  28.  * and two procedures that are called for moveto and curveto. I use d = 3.0
  29.  * and e = 0.2. d controls the slope of the curve depending on the neighbours
  30.  * (it's not prob. worth futzing with it) and e controls the shape of the ends
  31.  * of the curve. Experimenting with e may be fruitful.
  32.  * This is NOT an approximation algorithm. Given n points, it ALWAYS generates
  33.  * n-1 splines that pass through all the given points. For some sort of
  34.  * optimum approximation, see the paper in "Graphics Gems", Klossner ed. (It's
  35.  * the last source-code in the Appendix.)
  36.  *
  37.  * The callback procedures can be something like:
  38.  * void moveto(x, y)
  39.  * double x, y;
  40.  * {
  41.  *    printf("%g %g moveto\n", x, y);
  42.  * }
  43.  * void curveto(x1, y1, x2, y2, x3, y3)
  44.  * double x, y;
  45.  * {
  46.  *    printf("%g %g %g %g %g curveto\n", x1, y1, x2, y2, x3, y3);
  47.  * }
  48.  *
  49.  */
  50.  
  51. #include "plotfoil.h"
  52. #include "externs.h"
  53.  
  54. void interpolate(p, npoints, d, e, moveto, curveto)
  55. point_t *p;
  56. int npoints;
  57. double d, e;
  58. void (*moveto)(), (*curveto)();
  59. {
  60.    int i;
  61.    point_t slope_prev, slope_next;
  62.    point_t cp[MAXPOINTS], cpp[MAXPOINTS];
  63.    double l[MAXPOINTS];
  64.  
  65.    l[1] = sqrt(sqr(p[0].x-p[1].x)+sqr(p[0].y-p[1].y));
  66.    slope_prev.x = p[1].x - p[0].x;
  67.    slope_prev.y = p[1].y - p[0].y;
  68.    for(i = 1; i < npoints-1; i++) {
  69.       point_t slope;
  70.       double m;
  71.       
  72.       l[i+1] = sqrt(sqr(p[i].x-p[i+1].x)+sqr(p[i].y-p[i+1].y));
  73.  
  74.       slope_next.x = p[i+1].x - p[i].x;
  75.       slope_next.y = p[i+1].y - p[i].y;
  76.       
  77.       /*
  78.        * Slope of the curve at this point is the weighted ave. of
  79.        * straight-line slopes to neighbours (weighted by length of chord)
  80.        */
  81.  
  82.       slope.x = slope_prev.x * l[i+1] + slope_next.x * l[i];
  83.       slope.y = slope_prev.y * l[i+1] + slope_next.y * l[i];
  84.       
  85.       slope_prev = slope_next;
  86.  
  87.       /*
  88.        * Alternative method:
  89.        * Parameters:
  90.        *  a 0     Higher number makes curve tighter. -1<a<1.
  91.        *  b .1    Higher number makes sharp curves tighter
  92.        *          and broad curves less tight. -1<b<1
  93.        *       
  94.        * Given points A B and C, bezier control points for B are aligned along
  95.        * a line that is perpendicular to the line the bisects the angle ABC.
  96.        * The distance of the control points from B is determined by the
  97.        * following formula that was found by trial and error is has no
  98.        * particular theory behind it:
  99.        * Distance of control point from B towards A =
  100.        *    (1/2)*(distance between A and B)*
  101.        *       (cos(ABC)^(a*b + a + b))(b + 2(1-b)(1-a)/(3-a))
  102.        * (Timothy van Zandt <tvz@princeton.edu>)
  103.        * My opinion: one has to take an inverse cosine and raise it to a
  104.        * fractional power, and the results are very close to my simpler
  105.        * algorithm, so I don't think it's worth it. If someone decides to
  106.        * implement this, please let me know!
  107.        */
  108.       
  109.       /* Now we have slope: m is for the normalisation. */
  110.       m = sqrt(sqr(slope.x)+sqr(slope.y));
  111.       cp[i].x = p[i].x - l[i]*slope.x/(d*m);
  112.       cp[i].y = p[i].y - l[i]*slope.y/(d*m);
  113.       cpp[i].x = p[i].x + l[i+1]*slope.x/(d*m);
  114.       cpp[i].y = p[i].y + l[i+1]*slope.y/(d*m);
  115.    }
  116.    cpp[0].x = (e*cp[1].x + p[0].x)/(1+e);
  117.    cpp[0].y = (e*cp[1].y + p[0].y)/(1+e);
  118.    cp[npoints-1].x = (e*cpp[npoints-2].x + p[npoints-1].x)/(1+e);
  119.    cp[npoints-1].y = (e*cpp[npoints-2].y + p[npoints-1].y)/(1+e);
  120.  
  121.    (*moveto)(p[0].x, p[0].y);
  122.    for(i = 1; i < npoints; i++)
  123.       (*curveto)(cpp[i-1].x, cpp[i-1].y, cp[i].x, cp[i].y, p[i].x, p[i].y);
  124. }
  125.  
  126.